An Internet protocol (IP) network is a large distributed system in which individual routers automatically adjust their decisions on how to forward packets, or units of data, based on information they learn from their neighboring routers about the state of the network. This design permits rapid recovery in case of link or router failures by allowing affected routers to re-route packets around a failure as soon as they discover it. The Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) or the Intermediate System to Intermediate System (IS-IS) routing protocols are all commonly used embodiments of this design.
However, the distributed mode of operation of such routing protocols makes it difficult for a network administrator to have a global view of the network at any given time, and in particular of which traffic is flowing over which sets of links. Because of this, many network management functions that are available for networks based on more traditional technologies, e.g., connection-oriented technologies such as frame relay or asynchronous transfer mode (ATM), are difficult if not impossible to replicate in IP networks. For example, in a connection-oriented network, the state associated with each connection/user provides the network administrator with a ready handle for tracing its path and monitoring the associated volume of traffic it generates and the resources it consumes in the network, as well as determining the users and services impacted by the failure of network elements. Moreover, the connection-oriented nature of such networks ensures that the impact of failures is containable, inasmuch as connections not traversing the failing elements are not impacted by their failure.
In contrast routing decisions in IP networks are made in a distributed fashion by many routers that are only concerned with local packet forwarding decisions. There is no single entity with complete knowledge of the entire path that a packet will follow at any given time. This makes it difficult for a network administrator to precisely identify the path that the traffic between, for example, two customer sites, is following when traversing the network.
As a consequence, upon identifying a highly congested link, a network administrator has little or no visibility into which customers may be contributing to this congestion and to what extent. Similarly, in the presence of a link failure, identifying how the re-routing of traffic from customers affected by the failure will in turn impact other customers and by how much is again a very complex task.
Management tools do exist for IP networks, but they typically operate at a coarse granularity. In other words, they are not able to isolate the contributions of individual users, or they are limited to local measurements and do not provide an end-to-end or system-wide perspective. For example, routers typically support standard Management Information Bases (MIBs) that can be queried using protocols such as the Simple Network Management Protocol (SNMP). MIBs provide detailed state information about individual routers, e.g., interface status, number of packets or bytes transmitted and received on each interface, etc. However, this information is not only local to each device, but it is also aggregate in that it does not distinguish between the individual users whose traffic is traversing the interface. Conversely, traffic monitoring systems such as Cisco's NetFlow™ or Juniper cflowd™ are capable of capturing detailed, per-user information about the traffic crossing a given interface. However, extending this information to other interfaces in the network is not feasible and requires that traffic monitoring be carried out on every single interface throughout the network. This is typically an impractical task.
A few tools exist that allow end-to-end sampling of paths traversing an IP network. Most of them are based on two core utilities built into the Internet Protocol, ping and traceroute, which allow a network administrator to probe the network in order to generate estimates of end-to-end performance measures. Specifically, ping uses probe packets to record performance measures such as packet loss and delay along a specified path, but does not couple those measurements to internal network information. Similarly, traceroute constructs end-to-end path information, i.e., set of interfaces traversed, between a given starting point and a specified destination address. This path information can then be combined with either MIB or traffic monitoring information to generate path level performance estimates. However, it still does not provide complete visibility into which user traffic is traversing which interfaces. Providing such a capability would require identifying all possible paths through the network, which is not feasible using a solution based on traceroute.
Accordingly, it is desirable to provide an improved method and system for monitoring and tracking the set of interfaces or links through which traffic from specific customers flows as it traverses an IP network.
The following is provided as additional background information about the Internet and Internet routing protocols to help the reader understand the context of the present invention:
The Internet is a global network that consists of multiple interconnected smaller networks or Autonomous Systems (AS) also called routing domains. Packets are units of data that are routed between an origin and a destination on the Internet. The delivery of packets across this Interconnection of Networks is carried out under the responsibility of the IP protocol suite. In particular, routing protocols are responsible for allowing routers to determine how best to forward packets toward their destination.
Internet routing protocols can be divided into intra-domain and inter-domain routing protocols, with inter-domain routing protocols communicating information between ASs, while intra-domain routing protocols are responsible for determining the forwarding of packets within each AS. The RIP, OSPF and IS-IS protocols are examples of intra-domain routing protocols, while the Border Gateway Protocol (BGP) is an example of an inter-domain routing protocol. This general architecture and the associated suite of protocols are rapidly becoming the de facto technology on which modem communication networks are built. This dominance extends from simple local area networks to large-scale, international carrier networks, and is largely due to the robustness and efficiency of networks built using it. In particular, IP networks are often referred to as “connectionless”, and the delivery of data packets to their intended destination is performed through a number of “independent” decisions made by the routers to which a packet is being forwarded.